/**
 * 凸包计算， 使用叉积法判断点三点是否在同一条直线
 * 负值表示顺时针，正值表示逆时针，0表示三点共线
 * @param {[number, number]} a
 * @param {[number, number]} b
 * @param {[number, number]} c
 * @returns {number}
 */
export function cross(a, b, c) {
  return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
}

/**
 * Andrew 算法
 * @param {number[][]} trees
 * @return {number[][]}
 */
export var outerTrees = function (trees) {
  if (trees.length < 4) return trees
  // 选从左向右
  trees.sort((a, b) => {
    if (a[0] - b[0] === 0) return a[1] - b[1]
    return a[0] - b[0]
  })
  const ans = [trees[0], trees[1]]
  // 从左向右遍历，连结出下边的线
  for (let i = 2; i < trees.length; i++) {
    const c = trees[i]
    while (ans.length > 1 && cross(ans[ans.length - 2], ans[ans.length - 1], c) < 0) {
      ans.pop()
    }
    ans.push(c)
  }
  // 从右向左遍历，连结出上边的线
  for (let i = trees.length - 2; i >= 0; i--) {
    const c = trees[i]
    while ((ans.length > 1, cross(ans[ans.length - 2], ans[ans.length - 1], c) < 0)) {
      ans.pop()
    }
    if (i !== 0) ans.push(c)
  }

  return Array.from(new Set(ans))
}

/**
 * Graham 算法 (官方题解)
 * @param {number[][]} trees
 * @return {number[][]}
 */
export var outerTrees2 = function (trees) {
  const n = trees.length
  if (n < 4) {
    return trees
  }
  let bottom = 0
  /* 找到 y 最小的点 bottom*/
  for (let i = 0; i < n; i++) {
    if (trees[i][1] < trees[bottom][1]) {
      bottom = i
    }
  }
  trees = swap(trees, bottom, 0)
  /* 以 bottom 原点，按照极坐标的角度大小进行排序 */
  trees.sort((a, b) => {
    let diff = cross(trees[0], a, b) - cross(trees[0], b, a)
    return diff === 0 ? distance(trees[0], a) - distance(trees[0], b) : diff > 0 ? 1 : -1
  })
  /* 对于凸包最后且在同一条直线的元素按照距离从小到大进行排序 */
  let r = n - 1
  while (r >= 0 && cross(trees[0], trees[n - 1], trees[r]) === 0) {
    r--
  }
  for (let l = r + 1, h = n - 1; l < h; l++, h--) {
    trees = swap(trees, l, h)
  }
  const stack = [trees[0], trees[1]]
  for (let i = 2; i < n; i++) {
    let top = stack.pop()
    /* 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素 */
    while (cross(stack[stack.length - 1], top, trees[i]) > 0) {
      top = stack.pop()
    }
    stack.push(top)
    stack.push(trees[i])
  }
  return stack
}

function distance(p, q) {
  return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])
}

function swap(trees, i, j) {
  let temp0 = trees[i][0],
    temp1 = trees[i][1]
  trees[i][0] = trees[j][0]
  trees[i][1] = trees[j][1]
  trees[j][0] = temp0
  trees[j][1] = temp1
  return trees
}
